// 邻接表实现图，还包括BFS DFS遍历并输出

#include "myHeader.h"

static int visited[MAXVNUMBER] = {0};

using namespace std;

typedef char DataType;      // 顶点存储的数据类型设为字符型

typedef struct ENode *PtrToENode;
struct ENode     // 边的定义
{
    int V1, V2;  // 有向边<V1, V2>, 用顶点下标表示顶点
    int Weight;  // 权重
    friend bool operator < (const ENode &a, const ENode &b)  // 重载 < 运算符
    {
        return a.Weight > b.Weight;
    }
};
typedef PtrToENode Edge;

typedef struct AdjVNode *pAdjNode;
struct AdjVNode     // 邻接点的定义
{
    int AdjV;       // 邻接点下标
    int Weight;     // 边权重
    pAdjNode Next;  // 指向下一个邻接点的指针
};

typedef struct Vnode        // 顶点表头结点的定义
{
    pAdjNode FirstEdge;     // 边表头指针
    DataType Data;          // 存顶点的数据
} AdjList[MAXVNUMBER];      // AdjList是邻接表类型

typedef struct GNode *PtrToGNode;    // 以邻接表存储的图类型
struct GNode
{
    int Nv;     // 顶点数
    int Ne;     // 边数
    AdjList G;  // 邻接表
};
typedef PtrToGNode LGraph; // 以邻接表方式存储的图类型

void clearVisitedArr()  // 清空visited数组
{
    for(int i=0; i<MAXVNUMBER; i++)
        visited[i] = 0;
}

LGraph CreateGraph(int intNum) // 初始化一个有intNum个顶点，但没有边的图
{
    int V;
    LGraph Graph;

    Graph = new GNode(); // 建立图
    Graph->Nv = intNum;
    Graph->Ne = 0;

    for (V=0; V < Graph->Nv; V++)   // 默认顶点编号从0到(Graph->Nv - 1)
        Graph->G[V].FirstEdge = nullptr;

    return Graph;
}

void InsertEdge(LGraph Graph, Edge E) // 插入新边
{
    pAdjNode NewNode;

    // 为V2建立新的邻接点
    NewNode = new AdjVNode();
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;
    // 将V2插入V1的表头
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;

    NewNode = nullptr;

    // 无向图还要插入边 <V2, V1>
    // 为V1建立新的邻接点
    NewNode = new AdjVNode();
    NewNode->AdjV = E->V1;
    NewNode->Weight = E->Weight;
    // 将V1插入V2的表头
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

LGraph BuildGraph() // 输入图的数据
{
    LGraph Graph;
    Edge E;
    int V;
    int Nv, tempNe, choice, i;

    cin >> Nv >> tempNe;   // 读入顶点个数, 读入边数
    Graph = CreateGraph(Nv); // 初始化有Nv个顶点但没有边的图

    Graph->Ne = tempNe;

    if (Graph->Ne != 0)  // 如果有边
    {
        E = new ENode; // 建立边结点
        for (i=0; i<Graph->Ne; i++)
        {
            cin >> E->V1 >> E->V2;
            InsertEdge(Graph, E);
        }
    }
    return Graph;
}

void FindPathDFS(LGraph M, int u, int v)  // 非递归DFS，其中d表示path中的路径长度，初始值为-1
{
    clearVisitedArr();  // 清空visited数组

    visited[u] = 1;
    cout << u << "-->";

    stack<int> S = {};
    S.push(u);

    while (!S.empty())
    {
        int k = S.top();
        S.pop();

        if (!visited[k])
        {
            visited[k] = 1;
            cout << k << "-->";
        }

        for(int i=0; i<M->Nv; i++)
        {
            for(pAdjNode p = M->G[i].FirstEdge; p; p = p->Next)
            {
                int j = p->AdjV;
                if(!visited[j])
                    S.push(j);
            }
        }
    }
    cout << "END" << endl;
}

void FindPathBFS(LGraph M, int u, int v)  // 非递归BFS
{
    clearVisitedArr();  // 清空visited数组

    visited[u] = 1;
    cout << u << "-->";
    queue<int> Q = {};
    Q.push(u);

    while(!Q.empty())
    {
        int w = Q.front();
        Q.pop();
        visited[u] = 1;

        for(int i=0; i<M->Nv; i++)
        {
            for(pAdjNode p = M->G[i].FirstEdge; p; p = p->Next)
            {
                int k = p->AdjV;
                if(!visited[k])
                {
                    Q.push(k);
                    visited[k] = 1;
                    cout << k << "-->";
                }
            }
        }
    }
    cout << "END" << endl;
}